\documentclass{beamer}

\usepackage[utf8x]{inputenc}
\usepackage{listings}
\usepackage{gnuplottex}
%\usetheme[secheader]{Marburg}

%\usetheme[height=7mm]{Rochester}


%\usetheme{Pittsburgh}
%\usecolortheme{seahorse}

%\usepackage{beamerthemeshadow}

\newcommand{\src}[2]
{	
\lstinputlisting[basicstyle=\scriptsize,language=#1]{#2}
}

\newcommand{\srcbig}[2]
{	
\lstinputlisting[basicstyle=\ttfamily\normalsize,language=#1]{#2}
}

\newcommand{\srclarge}[2]
{	
\lstinputlisting[basicstyle=\ttfamily\large,language=#1]{#2}
}

\newcommand{\srctiny}[2]
{	
\lstinputlisting[basicstyle=\ttfamily\scriptsize,language=#1]{#2}
}

\title{pHaskell: un lenguaje funcional para metaprogramación}
\author{Autor: Marcelo Caro \\ Director: Daniel Fridlender \\ Co-Director: Daniel Gutson}
\date{Mayo 2012}


\begin{document}
\maketitle


\frame{\frametitle{Agenda}\tableofcontents} 

\section{Introducción} 

\subsection{Metaprogramación} 

\begin{frame}
\frametitle{Definición}
La metaprogramación es la escritura de programas de computación que a su vez escriben o manipulan otros programas (o a ellos mismos), tanto datos como código.
Esta manipulación puede suceder tanto en tiempo de compilación como en tiempo de ejecución. 

\end{frame}

\subsection{Metaprogramación en C++} 

\begin{frame}
\frametitle{Reseña histórica: Metaprogramación en C++}

\begin{itemize}
 
\item La metaprogramación en C++ usando templates surgió en forma accidental: fue descubierta durante el proceso de estandarización del lenguaje. %Mientras se escribían las reglas de instanciación de templates, resultó  que el sistema de templates era Turing-completo (en principio capaz de computar cualquier función computable).

\item La primera demostración práctica y concreta de esto fue mediante un programa escrito por \textbf{Erwin Unruh} en el año 1994. 
%Este programa computaba números primos, aunque no compilaba, sino que presentaba su resultado como un error en tiempo de compilación.
\item Se puede consultar el código escrito por Erwin Unruh en el apéndice A.
\item Posteriormente en el año 1995, \textbf{Todd Veldhuizen}, escribió un artículo en donde sentó las bases de la técnica de metaprogramación con templates.
%Hasta aquí Erwin Unruh desarrolló un ejemplo de cómo en tiempo de compilación se podían realizar cálculos no triviales usando el mecanismo de templates de C++. Posteriormente en el año 1995, Todd Veldhuizen, escribió un artículo \cite{todd} en donde sentó las bases de la técnica de metaprogramación con templates. En dicho artículo se demuestra cómo se pueden hacer cómputos complejos y que el resultado de estos cómputos sea la síntesis de nuevos tipos o código a ser inyectado por el compilador.   

\item Si uno explora la técnica de metaprogramación con templates queda en evidencia que la forma en que se conciben los meta algoritmos se asemeja a la programación funcional, aunque su escritura es mucho mas compleja. 
%Este hecho quedará al descubierto a medida que se expongan algunos ejemplos de metaprogramas durante el desarrollo de esta tesis.

\end{itemize}

\end{frame}

\subsubsection{Templates en C++} 
\begin{frame}
\frametitle{Templates}
Antes de entrar de lleno en el diseño e implementación de pHaskell, vamos a introducir algunos conceptos de C++ sumamente necesario para el desarrollo de esta presentación. 
$ $\\
$ $\\
\textbf{Templates:} \\
Los templates son el mecanismo de C++ para implantar el paradigma de la \textbf{programación genérica}. Permiten que una clase o función trabaje con tipos de datos genéricos, especificándose más adelante cuales son los que se quieren usar. 

\end{frame}

\begin{frame}
Definición de una clase template:

\srcbig{C++}{../TesisDoc/src/intro_template.cpp}

\begin{itemize} 
 \item El template definido no es una clase, sino una clase templetizada. 
 \item Las clases templetizadas pueden convertirse en verdaderas clases mediante la instanciación de templates.
\end{itemize}

\end{frame}

\begin{frame}
Una vez que el template es definido  éste puede \textbf{instanciarse} para ser utilizado.\\
Al instanciar un template indicamos el tipo concreto que queremos usar para la instanciación particular. 
\srcbig{C++}{../TesisDoc/src/intro_template.cpp}
\srcbig{C++}{../TesisDoc/src/intro_template_instanciacion.cpp}

\end{frame}

\subsubsection{Metaprogramación utilizando Templates} 


\begin{frame}
\frametitle{Especialización de templates}

\begin{itemize}
 \item C++ permite definir y especializar clases templates para tipos mas específicos.
 \item Para más información acerca de especialización de templates referirse al estándar de C++. (sección 14.5.4.1) 
\end{itemize}


\end{frame}

\begin{frame}
%Por ejemplo, en el siguiente código se define el template llamado \textit{container} y luego lo especializamos para enteros. 

\src{C++}{../TesisDoc/src/intro_especializacion_templates.cpp}
$ $\\
\textit{container$\langle$\textbf{double}$\rangle$}\\
\textit{container$\langle$\textbf{int}$\rangle$} 
$ $\\
$ $\\
De esta manera cuando se instancia \textit{container$\langle$double$\rangle$}, se usa la definición genérica, pero si se instancia \textit{container$\langle$int$\rangle$} el compilador usará la definición mas especializada.


\end{frame}

\begin{frame}
\frametitle{Especialización no trivial de templates}
\src{C++}{intro_especializacion_templates_patternmatching.cpp}
\textit{container$\langle$\textbf{double}$\rangle$}\\
\textit{container$\langle$\textbf{int}$\rangle$} \\
\textit{container$\langle$vector$\langle$\textbf{int}$\rangle$ $\rangle$} \\
\textit{container$\langle$vector$\langle$vector$\langle$\textbf{int}$\rangle$ $\rangle$ $\rangle$} 
$ $\\
$ $\\
\end{frame}


\begin{frame}
\frametitle{Realizando cálculos en tiempo de compilación}
El siguiente código es la implementación en C++ de la conocida función factorial:
$ $\\
$ $\\
\srcbig{C++}{../TesisDoc/src/intro_tmp_factorial.cpp}

\end{frame}

\begin{frame}
\frametitle{Realizando cálculos en tiempo de compilación}
En el caso anterior, se evalúa la función factorial con una constante, por lo tanto el cálculo de factorial(4) se podría hacer en tiempo de compilación usando TMP:

\src{C++}{../TesisDoc/src/intro_tmp_factorial_TMP.cpp}

\end{frame}


\begin{frame}
\lstinputlisting[basicstyle=\ttfamily\scriptsize]{./examples/factorial/disasm_factorial.txt}
\end{frame}

\begin{frame}
\lstinputlisting[basicstyle=\ttfamily\scriptsize]{./examples/factorial/disasm_factorial_tmp.txt}
\end{frame}


\begin{frame}
\textbf{Generando código utilizando TMP:}\\
\textbf{Serie:} $\pi = 4*atn(1)$ = 4 * ( 1/1 -1/3 + 1/5 - 1/7... )
\srctiny{C++}{./examples/pi/pi.h}
\end{frame}

\begin{frame}
\srcbig{C++}{./examples/pi/main1000.cpp}
\end{frame}

\begin{frame}
\frametitle{Pros y Contras de la técnica TMP}

\begin{itemize}
	\item Tiempo de compilación vs Tiempo de ejecución.% Si bien se puede ganar en rendimiento al llevar cálculos complejo al momento de la compilación, hay que tener en cuenta que esto puede impactar negativamente en el tiempo de compilación y hacer que compilar el programa sea bastante mas lento.
	\item El metaprograma escrito con TMP, generalmente carece de buena legibilidad y resulta difícil de mantener.
        \item Dificultad a la hora de depurar.
\end{itemize}
\end{frame}

\section{pHaskell} 

\begin{frame}
\begin{center}
\textbf{\LARGE{pHaskell}}
\end{center}
\end{frame}


\begin{frame}
\frametitle{pHaskell}

El mecanismo de templates de C++ es lo suficientemente potente para permitir metaprogramación, pero \textbf{no fue diseñado para éste propósito}. 
Esto hace que TMP sea una \textbf{técnica difícil en C++}, su \textbf{sintaxis poco clara} y los metaprogramas resultan \textbf{difícil de mantener}. 

\end{frame}

\begin{frame}
\frametitle{pHaskell}


El propósito de esta Tesis es crear un lenguaje que permita \textbf{desarrollar metaprogramas para C++} y que éste lenguaje pueda ser utilizado incluso por personas que no sean expertas en C++. 
\end{frame}

\begin{frame}
\frametitle{pHaskell}

 \textbf{pHaskell} es un lenguaje inspirado en Haskell que contiene entre otras características: 
\begin{itemize}
 \item Sintaxis y semántica para realizar cálculo en forma funcional. 
 \item Sintaxis y semántica para desarrollar metaprogramas. 
\end{itemize}

%De esta manera los programadores de pHaskell pueden realizar cálculos complejos sobre estructuras de datos complejas de la misma forma que lo harían en haskell. 
$ $\\
Mediante el traductor de pHaskell, podemos convertir un programa escrito en pHaskell a su equivalente en C++ TMP.
  
\end{frame}

\begin{frame}
\frametitle{pHaskell}
Un metaprograma creado con pHaskell contiene básicamente dos secciones: 

\begin{itemize}
	\item \textbf{Sección funcional:} Es un conjunto de definiciones de funciones, es código casi idéntico a haskell.
	\item \textbf{Generatrices:} En ésta sección están las definiciones de las generatrices, básicamente una generatriz es el puente que une el motor funcional con la generación de código en tiempo de compilación. 
\end{itemize}
\end{frame}

\subsection{Utilización} 

\begin{frame}
\frametitle{Ejemplo: Factorial}

\srcbig{Haskell}{../TesisDoc/src/factorial.phs}
$ $\\
$ $\\
\textbf{Utilizando $phaskell$  se generará nuestro metaprograma para ser usado desde C++:}
$ $\\
$ $\\
$ \$phaskell~factorial.phs$
$ $\\
$ $\\
Al correr el comando \textit{phaskell} sobre el archivo $factorial.phs$ se genera un nuevo archivo llamado \textbf{factorial.phs.h}, este nuevo archivo contiene el metaprograma escrito en TMP para ser usado en C++. 

\end{frame}



\begin{frame}
\textbf{La forma de invocar este metaprograma desde un programa escrito en C++ es:}

\src{C++}{./factorialmain.cpp}



\textbf{Compilamos nuestro programa en C++:}
\\
$ \$g++ ~ main.cpp$
$ $\\
$ $\\
\textbf{Y ahora lo corremos:}
\\
$ \$./a.out~$ 
\\
$120$

\end{frame}



\subsection{Características} 


\begin{frame}
\begin{center}
\textbf{\LARGE{Características de pHaskell}}
\end{center}
\end{frame}


\begin{frame}
\frametitle{Características de PHaskell}
pHaskell toma cada definición que existe en el código fuente (.phs) y produce templates de C++ que conservan la misma semántica original. 
$ $\\
\includegraphics[scale=0.45]{../TesisDoc/figures/phaskell_layout2.png} 
\end{frame}


\begin{frame}
\frametitle{Funciones}
\srclarge{Haskell}{../TesisDoc/src/e1.hs}
\end{frame}

\begin{frame}
\frametitle{Funciones currificadas}
\srclarge{Haskell}{../TesisDoc/src/e2.hs}
\end{frame}

\begin{frame}
\frametitle{Funciones como valores de primer orden}
\srcbig{Haskell}{../TesisDoc/src/e3.hs}
\end{frame}

\begin{frame}
\frametitle{Expresiones lambda}
\srcbig{Haskell}{../TesisDoc/src/e4.hs}
\end{frame}

\begin{frame}
\frametitle{Expresiones IF/ELSE}
\srcbig{Haskell}{../TesisDoc/src/e5.hs}
\end{frame}


\begin{frame}
\frametitle{Definición de funciones usando guardas}
\srclarge{Haskell}{../TesisDoc/src/e6.hs}
\end{frame}


\begin{frame}
\frametitle{Pattern matching}
\srclarge{Haskell}{../TesisDoc/src/e7.hs}
\end{frame}

\begin{frame}
\frametitle{Soporte nativo para listas}
\srclarge{Haskell}{../TesisDoc/src/e8.hs}
$ $\\
$ $\\
\srclarge{Haskell}{../TesisDoc/src/e9.hs}
\end{frame}


\begin{frame}
\frametitle{Definiciones locales en funciones}
pHaskell difiere de Haskell en que el las definiciones locales se sitúan entre las palabras reservadas \textbf{where} y \textbf{end}.
\srclarge{Haskell}{../TesisDoc/src/e10.hs}
\end{frame}

\begin{frame}
\frametitle{Tipos definidos por el usuario, y pattern matching}
\src{Haskell}{../TesisDoc/src/e11.hs}
\end{frame}

\begin{frame}
\frametitle{Evaluacion Lazy}

\srclarge{Haskell}{../TesisDoc/src/e12.hs}

%Cuesta creerlo, pero se puede conseguir que la instanciación de templates sea ``lazy''.
%Para lograrlo utilizamos una combinación de herencia y definición de tipos (\textbf{typedef}). 
\end{frame}



\subsection{Metaprogramación: Generatrices} 

\begin{frame}
\frametitle{Generatrices: Generando código en tiempo de compilación}

A continuación se verá como podemos generar código en tiempo de compilación utilizando pHaskell. Para tal motivo se introducirá  el concepto de \textbf{generatriz}.
$ $\\

%\textbf{Expresión constante:} Es una expresión que puede calcularse en tiempo de compilación [std 5.19 Constant expressions]. Por ejemplo el siguiente código en C++: $x=2+2$, puede resolverse en tiempo de compilación y usarse su equivalente $x=4$, ya que 2+2 es una expresión constante y el compilador puede evaluarla en tiempo de compilación. 
%$ $\\
%Existen reglas que gobiernan las expresiones constantes, y estas pueden ser no integrales. 
\end{frame}

\begin{frame}
Una generatriz es una función que tiene la siguiente forma:  
$ $\\
$ $\\
$\{\textbf{retorno}\}$ \textbf{nombre} $p_1~  \ldots~ p_n~$ $\{T_1~ rt_1,~ \ldots~ ,~ T_N~ rt_n \}$  =  $\textbf{cuerpo}$
$ $\\

\begin{itemize}
	\item $p_1~ p_2~ \ldots~ p_n~$: Son parámetros de tiempo de compilación.
        \item $\{T_1~ rt_1,~ T_2~ rt_2,~ \ldots~ ,~ T_N~ rt_n \}$:  $rt_i$ Son parámetros de tiempo de ejecución y $T_i$ es el tipo de cada parámetro. Estos parámetros puedes ser utilizado para llamar otra generatriz, para hacer operaciones matemáticas. Etc. 
	\item $\{\textbf{retorno}\}$: Es el tipo del valor que retorna la generatriz, es un valor en tiempo de ejecución.
        \item $\textbf{cuerpo}$: Es la parte de la generatriz en donde se expresa la semántica de metaprogramación. El cuerpo de una generatriz se evalúa parte en tiempo de compilación y parte en tiempo de ejecución. 
\end{itemize}
\end{frame}

\begin{frame}
$ $\\
Una generatriz es una función con sintaxis y semántica ampliada para \textbf{permitir metaprogramación}.$ $\\
pHaskell convierte cada generatriz a una función para ser usada desde un programa en C++. El cuerpo de una generatriz se ejecuta parte en tiempo de compilación y parte en tiempo de ejecución.
$ $\\
\end{frame}


\begin{frame}
\frametitle{Invocando generatrices desde generatrices}
Para invocar una generatriz desde un metaprograma escrito en pHaskell, se hace utilizando la siguiente siguiente sintaxis:
$ $\\
$\{nombre~ p_1~ p_2~ \ldots~ p_n\}(e_1,~ e_2,~ \ldots~, ~e_n)$
$ $\\
En donde $p_1~ p_2~ \ldots~ p_n$ son parámetros disponibles en tiempo de compilación y  $e_1,~ e_2,~ \ldots~, ~e_n$ son parámetros disponibles en tiempo de ejecución.

Para invocar funciones normales de pHaskell:
$ $\\
\src{Haskell}{../TesisDoc/src/llamada_a_funcion_desde_generatriz2.phs}
$ $\\
Hacerlo de esta forma resulta un poco obscuro, pero funciona. En futuras revisiones de pHaskell se buscaran alternativas para hacer este tipo de invocación en forma mas directa.


\end{frame}


\begin{frame}
\frametitle{Pattern matching en parámetros de generatrices}
\src{Haskell}{../TesisDoc/src/genpatternmatching.phs}

\end{frame}


\begin{frame}
\frametitle{Concatenación de expresiones}
Dentro de una generatriz, a diferencia de una función en pHaskell, existe una noción de \textbf{estado}. Dicha noción viene dada por los parámetros en tiempo de ejecución. Por lo tanto dentro de una generatriz pueden haber expresiones con efecto colaterales. 
Dentro de una generatriz podemos concatenar expresiones, mediante el operador \textbf{``;''} de la siguiente manera:
$e_1;~e_2; \ldots ;e_n$, en este caso se evalúan $e_1$ hasta $e_n$ y se descartan los valores retornados salvo en de $e_n$ que pasa a ser el valor de toda la expresión.

\end{frame}


\subsection{Ejemplos} 
\begin{frame}
\frametitle{Ejemplo: Un factorial ampliado}
\src{Haskell}{genfactorial2.phs}
\end{frame}

\begin{frame}
\frametitle{Ejemplo: Generar el código que llena un vector}
\srctiny{Haskell}{concat_operator.phs}
El este ejemplo se genera una función cuyo código llena un vector con el valor del parámetro ``v``. Y retorna ''count``
\end{frame}


\begin{frame}
\frametitle{Ejemplo: Generar código para llenar un vector II}

El propósito del siguiente ejemplo es construir una generatriz que genere el código para llenar un vector con \textbf{números consecutivos}. En tiempo de compilación ya sabemos el rango del vector y la generatriz debe generar los valores e insertarlo. 
\\
Una ventaja de hacer un metaprograma para llenar un vector, es que en tiempo de compilación el compilador puede hacer \textbf{inline} de las llamadas recurrentes, evitando hacer saltos innecesarios.
\\

\end{frame}


\begin{frame}
\srctiny{Haskell}{myactive.phs}

\end{frame}


\begin{frame}
\textbf{Generación del metaprograma:}
$ $\\
\textit{$>$ phaskell myactive.phs}
$ $\\
$ $\\
\textbf{Invocación del metaprograma desde main.cpp}
\src{C++}{../TesisDoc/src/first_active_library/main.cpp}
\end{frame}


\begin{frame}
Función que utiliza un bucle para llenar el vector es: 
\lstinputlisting[basicstyle=\ttfamily\scriptsize]{./examples/gencode/no_tmp.txt}
\end{frame}

\begin{frame}
El desensamblado de el metaprograma: 
\lstinputlisting[basicstyle=\ttfamily\scriptsize]{./examples/gencode/tmp.txt}
\end{frame}


\subsection{Caso de uso: SHA1} 

\begin{frame}
\frametitle{SHA1}
El algoritmo propuesto por la \textbf{RFC3174}, esta compuesto por una función principal llamada \textbf{SHA1ProcessMessageBlock} que es la que realiza la mayor cantidad de cálculos. El resto de la implementación son funciones auxiliares para rellenar, inicializar estructuras. etc.

En este ejemplo de demostración se reescribió la función \textbf{SHA1ProcessMessageBlock} utilizando una generatriz:
\end{frame}

\begin{frame}
\srctiny{Haskell}{./sha1_2.phs}
\end{frame}


\begin{frame}
\srctiny{Haskell}{./sha1.phs}
\end{frame}

\begin{frame}
El siguiente gráfico representa una medición de la eficiencia realizada en una PC corriendo Ubuntu 11.00, con micro Intel Core II y 2Gb de RAM.
$ $\\
$ $\\
\includegraphics[scale=0.45]{sha1.png} 

\end{frame}

\section{Implementación de pHaskell}

\begin{frame}
\begin{center}
\textbf{\LARGE{Implementación de pHaskell}}
\end{center}
\end{frame}



\begin{frame}
\frametitle{Implementación de pHaskell}
pHaskell esta desarrollado utilizando Haskell como lenguaje (\textbf{GHC}) y el generador de parser \textbf{Happy}. pHaskell está configurado para instalarse como un paquete cabal.
$ $\\
$ $\\
Se puede acceder al código fuente de la siguiente manera:
$ $\\
$ $\\
\small{
\textit{\textbf{: svn checkout https://phaskell2.googlecode.com/svn/trunk/ phaskell --username user@gmail.com}}
}
$ $\\
$ $\\
Una vez obtenido el código fuente, puede compilarse e instalarse con la siguiente instrucción.
$ $\\
$ $\\
\textit{\textbf{: cabal install phaskell}}
$ $\\
$ $\\
Una vez corrido este comando, se tendrá pHaskell compilado e instalado, listo para ser utilizado.

\end{frame}

\begin{frame}
\frametitle{Transformaciones}
El traductor se basa en ir transformando abstracciones, y cada paso de transformación produce resultados que están mas alejado de pHaskell y mas cerca de TMP. Cada transformación toma una entrada expresada en cierto tipo y devuelve una nueva abstracción del programa expresado en otro tipo de dato. Los tipos fundamentales sobre los cuales estas transformaciones actúan son:

\begin{itemize}
 \item \textbf{\textit{String}}
 \item \textbf{\textit{Program}}
 \item \textbf{\textit{LProgram}}
 \item \textbf{\textit{MetaProgram}}
 \item \textbf{\textit{String}}
\end{itemize}

\end{frame}


\begin{frame}
\includegraphics[scale=0.35]{../TesisDoc/figures/abs.pdf}  
\end{frame}


\begin{frame}
\frametitle{Organización del código fuente}

\begin{itemize}
\item \textbf{PHaskellParser.y}: Parser.
\item \textbf{Main.hs}: Punto de entrada del programa traductor. 
\item \textbf{Fase1.hs}: Transformaciones de la fase 1.
\item \textbf{Fase2.hs}: Transformaciones de la fase 2. 

\item Tipos de datos:
\begin{itemize}
 \item \textbf{Lambdatypes.hs}
 \item \textbf{PHaskellTypes.hs}
 \item \textbf{TemplatesTypes.hs}
\end{itemize}

\item \textbf{LambdaLifting.hs}: Transforma expresiones lambdas en definiciones locales.       
\item \textbf{TemplateRender.h}: Genera el TMP correspondiente a las definiciones de funciones.  
\item \textbf{GeneratrixRender.hs}: Genera el TMP correspondiente a las definiciones de generatrices.      

\end{itemize}
\end{frame}



\begin{frame}
\includegraphics[scale=0.35]{../TesisDoc/figures/fases2.pdf} 
\end{frame}

\section{Traducción de pHaskell a TMP}

\begin{frame}
\begin{center}
\textbf{\LARGE{Traducción de pHaskell a TMP}}
\end{center}
\end{frame}


\begin{frame}
\frametitle{Traducción de pHaskell a TMP}
Gran parte del trabajo de esta tesis consistió en buscar forma de traducir funciones a templates que sea lo suficientemente completa para expresar:
\begin{itemize} 
	\item \textbf{Currificación de funciones} 
	\item \textbf{Funciones como valor de primer orden} 
	\item \textbf{Expresiones lambda} 
	\item \textbf{Pattern matching} 
	\item \textbf{Soporte para listas y Tipos definidos por el usuario} 
	\item \textbf{Definiciones locales} 
\end{itemize}
El traductor de pHaskell a TMP, debe convertir cada definición de pHaskell a TMP  de forma que conserve la semántica original dada en pHaskell.


\end{frame}



\begin{frame}
Supongamos que tenemos el archivo $ejemplo1.phs$ que contiene el siguiente código en phaskell.
$ $\\
\srcbig{Haskell}{../TesisDoc/src/ejemplo1.phs}
\end{frame}

\begin{frame}
Después de correr $phaskell$ tendremos el archivo $ejemplo1.phs.h$ con los siguientes templates:
$ $\\
\src{C++}{../TesisDoc/src/ejemplo1.phs.h}
\end{frame}

\begin{frame}
\frametitle{Equivalencia básica}

Una versión simplificada se vería de la siguiente manera: \\
\srcbig{C++}{ejemplo1_simplificado.phs.h}

\end{frame}


\begin{frame}
\frametitle{Equivalencia básica}

 La equivalencia básica utilizada por pHaskell es la siguiente: 

$ $\\
$|f~x~y = e|  ~~~ \models$\\
\src{C++}{principal_equivalencia.hs.h}
$ $\\
$\|f~x_1~\dots~x_N\| ~~~ \models$
\src{C++}{principal_equivalencia2.hs.h} 
$ $\\

\end{frame}


\begin{frame}
\frametitle{Especialización completa en templates anidados}
El estándar no permite especialización completa de templates anidados. Por ejemplo: 
$ $\\
\src{C++}{../TesisDoc/src/fullspe.cpp}
$ $\\
Cuando se intenta compilar el ejemplo anterior utilizando \textbf{gcc}, se obtiene este error:\\
$ $\\
$>$\textbf{error: explicit specialization in non-namespace scope 'struct Root'}\\

\end{frame}

\begin{frame}
Para remendar este error, se agrega un parámetro extra que no se utiliza pero hace que el template sea estándar y funcione en mas compiladores. Este nuevo parámetro se define con un valor por defecto para no tener que agregarlo en las instanciaciones:
$ $\\
\src{C++}{./fullspe2.cpp}
\end{frame}

\begin{frame}
\frametitle{El problema de los templates anidados}

En la equivalencia propuesta, funciones con varias variables se transforman a templates anidados, llamados \textbf{app}. Pero el estándar de C++ no permite anidar templates con el mismo nombre:


\src{C++}{../TesisDoc/src/nestedtemp.cpp}


Se obtiene este error:\\


\textbf{$>$error: 'Root$<$T$>$::app$<$T2$>$::app   has the same name as the class in which it is declared}
\end{frame}

\begin{frame}

Por tal motivo se tuvo que agregar una estructura mas en el anidamiento llamado \textbf{''\_``}. De este modo, pese a complicar la equivalencia de traducción de pHaskell a TMP, se evita el incumplimiento del estándar y se gana en compatibilidad con diferentes compiladores:


\src{C++}{../TesisDoc/src/nestedtemp2.cpp}

 

\end{frame}


\begin{frame}

 La equivalencia básica utilizada por pHaskell es la siguiente: 

$ $\\
$|f~x~y = e|  ~~~ \models$\\
\src{C++}{../TesisDoc/src/principal_equivalencia.hs.h}
$ $\\
\end{frame}

\begin{frame}
$ $\\
$\|f~x_1~\dots~x_N\| ~~~ \models$
\src{C++}{../TesisDoc/src/principal_equivalencia2.hs.h} 
$ $\\

\end{frame}

\begin{frame}
\begin{tabular}{lcl}
Sea $c_i$ una constante integral:\\
$\|c_i\| ~~~ \models~~ Int\langle c_i \rangle$ \\
$ $\\
$ $\\
Sea $c_b$ una constante booleana ($true, false$):\\
$\|c_b\| ~~~ \models~~ Bool\langle c_b \rangle$ \\
$ $\\
$ $\\
\end{tabular}  

\begin{tabular}{lcl}
$\|e_1~ +~ e_2\|$ & $\models$& $\| pAdd~e_1~e_2 \|  $\\ 
$\|e_1~ -~ e_3\|$& $\models$& $ \| pMinus~e_1~e_2 \|  $\\
$\|e_1~ *~ e_4\|$& $\models$& $ \| pMult~e_1~e_2 \|  $\\
$\|e_1~ /~ e_2\|$& $\models$& $ \| pDiv~e_1~e_2 \| $\\
\end{tabular}  

\end{frame}

\begin{frame}
\begin{tabular}{lcl}

$\|e_1~ \langle~  e_2\|$& $\models$& $ \| pLess~e_1~e_2 \|  $\\    
$\|e_1~ \langle=~ e_2\|$& $\models$& $ \| pLessEq~e_1~e_2 \|  $\\
$\|e_1~ \rangle~  e_2\|$& $\models$& $ \| pGreat~e_1~e_2 \|  $ \\
$\|e_1~ \rangle=~ e_2\|$& $\models$& $ \| pGreatEq~e_1~e_2 \|  $\\
$\|e_1~ ==~ e_2\|$& $\models$& $ \| pEq~e_1~e_2 \|  $\\   
$\|e_1~ !=~ e_2\|$& $\models$& $ \| pNotEq ~e_1~e_2 \|  $\\       
$\|e_1~ \mid\mid~ e_2\|$& $\models$& $ \| pOr~e_1~e_2 \|   $\\
$\|e_1~ \&\&~ e_2\|$& $\models$& $ \| pAnd~e_1~e_2 \|   $\\
$\|e_1~ \%~ e_2\|$& $\models$& $ \| pMod~e_1~e_2 \|   $\\
$ $\\
$ $\\
\end{tabular}  

\textit{\textbf{pAdd}, \textbf{pMinus}, \textbf{pMult} y todas las funciones mencionada anteriormente, se encuentran definidas en prelude.h}

\end{frame}


\begin{frame}
\frametitle{Pattern Matching}
El ''pattern matching`` en una función de pHaskell tiene su correspondencia con una especialización de template en C++. Cada caso de matching es un caso de especialización. 
\\
El \textbf{puente eager} es un paso previo a intentar el matching con la especialización de template en el cual se evalúa el parámetro en forma eager para obtener su representación canonica antes de hacer el matching.
\end{frame}


\begin{frame}

\textbf{Pattern matching con el puente eager:}
$ $\\
$|f~p_1 = e_1|$\\
$~~~ \vdots $\\
$|f~p_i = e_i|$\\
$~~~ \vdots $\\
$|f~p_N = e_N|$\\
$ $\\
$\models$\\
\end{frame}

\begin{frame}
\src{C++}{./pattern_matching_basic_generic.hs.h}
\end{frame}

\begin{frame}
\frametitle{Pattern Matching sobre multiple parametros}
%Cuando tenemos múltiples parámetros y pattern matching, es necesario generalizar la definición anterior utilizando un árbol de decisión.
$f~0~0~a~b = e_1$\\
$f~0~0~1~d = e_2$\\
$f~1~e~f~g = e_3$\\
$f~1~2~f~g = e_4$\\
$f~1~2~3~g = e_5$\\
$f~r~s~t~u = e_6$\\
$ $\\
Se obtiene los siguientes niveles de matching:
$ $\\
\begin{tabular}{lccccccc}
$ $\\
\textbf{f} & 0 & 0 & a & b & = & $e_1$ \\
\textbf{f} & 0 & 0 & 1 & d & = & $e_2$ \\
\textbf{f} & 1 & e & f & g & = & $e_3$ \\
\textbf{f} & 1 & 2 & f & g & = & $e_4$ \\
\textbf{f} & 1 & 3 & 3 & g & = & $e_5$ \\
\textbf{f} & r & s & t & u & = & $e_6$ \\
  & \textbf{Level 1} & \textbf{Level 2} & \textbf{Level 3} & \textbf{Level 4} &  & \textbf{Expresión} \\
\end{tabular}
\end{frame}

\begin{frame}

Se puede representar la función anterior como el siguiente árbol de decisión:\\
\includegraphics[scale=0.38]{../TesisDoc/figures/match_tree.pdf}
$ $\\

Una vez que se construye el árbol de decisión, traducir la definición de $f$ a TMP es ir anidando por niveles de matching en el árbol de decisión.


\end{frame}
\begin{frame}
\frametitle{Expresiones Lambda}
Si bien pHaskell soporta expresiones lambda, lo hace de una manera artificial. pHaskell preprocesa las expresiones lambda y las remplaza por funciones locales equivalentes.
$ $\\
$ $\\
$f~x= \dots ~ (\backslash x \rightarrow e )~\dots ~ $ \\
$\equiv $ \\
$f~x= \dots ~  e' ~\dots ~ $\\
\textbf{$~~~~~~ where$} \\
$~~~~~~~~ e'~x = e $\\
\textbf{$~~~~~~ end$ }\\
\end{frame}

\subsection{Traducción de Generatrices}

\begin{frame}
\frametitle{Traducción de Generatrices}
Una generatriz se traduce a una clase templetizada que contiene una función anidada. Esta función toma parámetros templetizado que le llamaremos parámetros de tiempo de compilación y parámetros no templetizados, parámetros comunes y corrientes de la función) que lo llamaremos parámetros en tiempo de ejecución.

\end{frame}

\begin{frame}
Por ejemplo:
$ $\\
$ $\\
%\srctiny{Haskell}{./generatrix_equivalence.hs}

\small{\{int\} gName p1 p2 p3 \{int rtp1, float rtp2\}=p1::c\_value*rpt1 }
$ $\\
$ $\\
$\models$\\
\src{C++}{./generatrix_equivalence.hs.h}

Como se mostró anteriormente, la equivalencia propuesta es simple: Los parámetros templetizados son evaluados buscando su $c\_value$, lo cual implicaría una evaluación eager de los mismos.

\end{frame}

\begin{frame}

Como se mostró anteriormente, la equivalencia propuesta es simple: Los parámetros templetizados son evaluados buscando su $c\_value$, lo cual implicaría una evaluación ''eager`` de los mismos.

$ $\\
\small{$|~~ \{r\_type\}~ gName~~ p_1~ \dots~ p_N~ \{type_1~ rtp_1, \dots , type_M~ rtp_M\}  =  e ~~|$ }\\
$\models$\\
\src{C++}{./generatrix_equivalence_general.hs.h}
$ $\\
\end{frame}

\begin{frame}
Sean $c_i$ una constante integral, $c_b$ una constante booleana y $e_1$ y $e_2$ expresiones:\\


\begin{tabular}{lcl}
$ $\\
$|[c_i]|$ & $\models$ & $ c_i$           \\  
$|[c_b]|$ & $\models$ & $ c_b$            \\
$|[v]|$ & $\models$ & $  v$       \\
$|[e_1 \langle  e_2]|$ & $\models$ & $ |[e_1]|~ \langle~ |[e_2]|$  \\
$|[e_1 * e_2]|$ & $\models$ & $ |[e_1]|~ *~ |[e_2]|$           \\
$|[e_1 / e_2]|$ & $\models$ & $ |[e_1]|~ /~ |[e_2]|$           \\
$|[e_1 + e_2]|$ & $\models$ & $ |[e_1]|~ +~ |[e_2]|$           \\
$|[e_1 - e_2]|$ & $\models$ & $ |[e_1]|~ -~ |[e_2]|$           \\
$|[e_1 . e_2]|$ & $\models$ & $ |[e_1]|~ .~ |[e_2]|$           \\
$|[e_1 \& e_2]|$ & $\models$ & $ |[e_1]|~ \&~ |[e_2]|$           \\
\end{tabular}
\end{frame}





\begin{frame}
\begin{tabular}{lcl}
$|[e_1 | e_2]|$ & $\models$ & $ |[e_1]|~ |~ |[e_2]|$           \\
$|[e_1 \wedge e_2]|$ & $\models$ & $ |[e_1]|~ \wedge~ |[e_2]|$           \\
$|[e_1 = e_2]|$ & $\models$ & $ |[e_1]|~ =~ |[e_2]|$           \\
$|[e_1 == e_2]|$ & $\models$ & $ |[e_1]|~ ==~ |[e_2]|$          \\
$|[e_1 \langle\langle e_2]|$ & $\models$ & $ |[e_1]|~ \langle\langle~ |[e_2]|$          \\
$|[e_1 ; e_2]|$ & $\models$ & $ |[e_1]|~ ,~ |[e_2]|$          \\
$|[e_1 \colon\colon e_2]|$ & $\models$ & $ |[e_1]|~ \colon\colon~ |[e_2]|$          \\
$|[~e_1 [e_2] ~]|$ & $\models$ & $  |[e_1]| ~[~ |[e_2]|~]$    \\
$|[~e_1(e_2)]|$ & $\models$ & $ |[e_1]| ~(~ |[e_2]|~)$  \\
$|[e_1 ? e_2 \colon e_3]|$ & $\models$ & $ |[e_1]|~ ?~ |[e_2]|~ \colon~ |[e_3]|$  \\
$|[ \sim e_1]|$ & $\models$ & $ \sim ~|[e_1]|$   \\    

\end{tabular}


\end{frame}



\begin{frame}
\frametitle{Próximas mejoras/nuevas características}

\begin{itemize}
  \item Soporte para C++11
  \item Chequeo fuerte de tipos.
  \item Soporte para la técnica ''Expression Templates``
  \item Full lazy.
\end{itemize}
\end{frame}


\end{document}
